// @algorithm @lc id=725 lang=cpp 
// @title split-linked-list-in-parts


// @test([1,2,3],5)=[[1],[2],[3],[],[]]
// @test([1,2,3,4,5,6,7,8,9,10],3)=[[1,2,3,4],[5,6,7],[8,9,10]]
class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* head, int k) {
        vector<ListNode*> ans(k, NULL);
        ListNode dumy(0, head), *p=&dumy;
        int n = 0;
        while(p=p->next) n++;
        int cnt = n/k, extra = n%k;
        p = &dumy;
        for(int i=0; i<k && p; i++){
            ans[i] = p->next;
            p->next = NULL;
            p = ans[i];
            for(int j=1; p && j<cnt+(i<extra?1:0); j++)
                p = p->next;
        }
        return ans;
    }
};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */